#include<cstdio>//uncle-lu
#include<algorithm>
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

int n, m;
int F[1010];
int v[1010][1010], w[1010][1010];
int cnt[1010], k;

int main()
{
	read(m);read(n);
	int a, b, c;
	for (int i = 1; i <= n; i++) 
	{
		read(a);read(b);read(c);
		if(c > k)
			k = c;
		cnt[c]++;
		v[c][cnt[c]] = a;
		w[c][cnt[c]] = b;
	}

	for (int t = 1; t <= k; t++) 
		for (int j = m; j >= 0; j--) 
			for (int i = 1; i <= cnt[t]; i++) 
				if(j >= v[t][i])
					F[j] = std::max(F[j], F[j - v[t][i]] + w[t][i]);

	printf("%d", F[m]);
	return 0;
}
